/*
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

 

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
 

提示：

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
*/

class Solution {
public:
    void balance(vector<int> &nums,int i,int heapsize){ //处理节点i与他的子节点 若是i比他的子节点大则交换
        int l=2*i+1,r=2*i+2,large=i;

        if(l<heapsize&&nums[l]>nums[large]) large=l;
        if(r<heapsize&&nums[r]>nums[large]) large=r;

        if(large!=i){
            swap(nums[i],nums[large]);
            balance(nums,large,heapsize);
        }
    }

    void makeheap(vector<int> &nums,int heapsize){
        for(int i=heapsize/2-1;i>=0;i--){ //最重要的 将i设为堆的大小heapsize/2-1(刚好为第一个非叶子节点)
            balance(nums,i,heapsize);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        int heapsize=nums.size();

        makeheap(nums,heapsize);
        for(int i=0;i<k-1;i++){
            swap(nums[0],nums[heapsize-1]);

            heapsize--;
            balance(nums,0,heapsize);
        }

        return nums[0];
    }
};